#include "ext2.h"
#include <asm/bitops.h>
#include <cnix/log2.h>
#include <cnix/string.h>
#include <cnix/errno.h>

#define SB_BLOCK	(1)
extern void ext2_rsv_window_add(struct super_block *sb,
        struct ext2_reserve_window_node *rsv);
extern unsigned long ext2_new_blocks(struct inode *inode,ext2_fsblk_t,unsigned long*);
extern void ext2_free_blocks(struct inode *,unsigned long,unsigned);
extern struct inode_operation ext2_inode_operation;
static BOOLEAN ext2_init(struct super_block * sb, dev_t dev);
static void ext2_free(struct super_block *);
static BOOLEAN ext2_iread(struct inode *inoptr, dev_t dev, ino_t ino);
static BOOLEAN ext2_iwrite(struct inode *, dev_t, ino_t);
static BOOLEAN ext2_ialloc(void*, struct inode *, mode_t);
static void 	 ext2_ifree(struct super_block*, struct inode*);
static unsigned long ext2_balloc(void*);
static void ext2_bfree(void*, unsigned long);
static int ext2_statfs(struct super_block *, struct statfs *);

struct filesystem ext2_filesystem = {
	.init = ext2_init,
	.free = ext2_free,
	.iread = ext2_iread,
	.iwrite= ext2_iwrite,
	.ialloc= ext2_ialloc,
	.ifree = ext2_ifree,
	.balloc= ext2_balloc,
	.bfree = ext2_bfree,
	.statfs= ext2_statfs,
};

static inline int test_root(int a, int b)
{
  int num = b;

  while (a > num)
    num *= b;
  return num == a;
}

static int ext2_group_sparse(int group)
{
  if (group <= 1)
    return 1;
  return (test_root(group, 3) || test_root(group, 5) ||
    test_root(group, 7));
}

/**
 *  ext2_bg_has_super - number of blocks used by the superblock in group
 *  @sb: superblock for filesystem
 *  @group: group number to check
 *
 *  Return the number of blocks used by the superblock (primary or backup)
 *  in this group.  Currently this will be only 0 or 1.
 */   
int ext2_bg_has_super(struct ext2_sb_info *sbi, int group)
{ 
  if (EXT2_HAS_RO_COMPAT_FEATURE(sbi,EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER)&&
      !ext2_group_sparse(group))
    return 0;
  return 1;
}

struct ext2_group_desc * ext2_get_group_desc(struct ext2_sb_info * sbi,
               unsigned int block_group,
               u8_t ** bh)
{       
  unsigned long group_desc;
  unsigned long offset;
  struct ext2_group_desc * desc;
            
  if (block_group >= sbi->s_groups_count) {
    printk("ext2_get_group_desc",
          "block_group >= groups_count - "
          "block_group = %d, groups_count = %lu",
          block_group, sbi->s_groups_count);

    return NULL;
  }
  group_desc = block_group >> sbi->s_desc_per_block_bits;
  offset = block_group & (sbi->s_desc_per_block - 1);
  if (!sbi->s_group_desc[group_desc]) {
    printk("ext2_get_group_desc",
          "Group descriptor not loaded - "
          "block_group = %d, group_desc = %lu, desc = %lu",
           block_group, group_desc, offset);
    return NULL;
  }

  desc = (struct ext2_group_desc *) sbi->s_group_desc[group_desc];
  if (bh)
    *bh = sbi->s_group_desc[group_desc];
  return desc + offset;
}

static int ext2_check_descriptors(struct ext2_sb_info *sbi)
{
  int i;

  for (i = 0; i < sbi->s_groups_count; i++) {
    struct ext2_group_desc *gdp = ext2_get_group_desc(sbi, i, NULL);
    ext2_fsblk_t first_block = ext2_group_first_block_no(sbi, i);
    ext2_fsblk_t last_block;

    if (i == sbi->s_groups_count - 1)
      last_block = sbi->s_es->s_blocks_count - 1;
    else
      last_block = first_block +
        (sbi->s_blocks_per_group - 1);

    if (gdp->bg_block_bitmap < first_block ||
        gdp->bg_block_bitmap > last_block)
    {
      printk("ext2_check_descriptors Block bitmap for group %d not in group (block %u)\n",
            i, (unsigned long) (gdp->bg_block_bitmap));
      return 0;
    }
    if (gdp->bg_inode_bitmap < first_block ||
        gdp->bg_inode_bitmap > last_block)
    {
      printk("ext2_check_descriptors",
            "Inode bitmap for group %d"
            " not in group (block %lu)!",
            i, (unsigned long) (gdp->bg_inode_bitmap));
      return 0;
    }
    if (gdp->bg_inode_table < first_block ||
        gdp->bg_inode_table + sbi->s_itb_per_group - 1 >
        last_block)
    {
      printk("ext2_check_descriptors",
            "Inode table for group %d"
            " not in group (block %lu)!",
            i, (unsigned long) gdp->bg_inode_table);
      return 0;
    }
  }
  return 1;
}

static unsigned long descriptor_loc(struct ext2_sb_info *sbi,
            unsigned long logic_sb_block,
            int nr)
{
  unsigned long bg, first_meta_bg;
  int has_super = 0;

  first_meta_bg = sbi->s_es->s_first_meta_bg;

  if (!EXT2_HAS_INCOMPAT_FEATURE(sbi, EXT2_FEATURE_INCOMPAT_META_BG) ||
      nr < first_meta_bg)
    return (logic_sb_block + nr + 1);
  bg = sbi->s_desc_per_block * nr;
  if (ext2_bg_has_super(sbi, bg))
    has_super = 1;

  return ext2_group_first_block_no(sbi, bg) + has_super;
}

/* Called at mount-time, super-block is locked */
unsigned long ext2_count_dirs (struct super_block * sb)
{   
  unsigned long count = 0;
  int i;
  
  for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
    struct ext2_group_desc *gdp = ext2_get_group_desc (EXT2_SB(sb), i, NULL);
    if (!gdp)
      continue;
    count += le16_to_cpu(gdp->bg_used_dirs_count);
  }
  return count;
}

unsigned long ext2_count_free_blocks (struct super_block * sb)
{
  struct ext2_group_desc * desc;
  unsigned long desc_count = 0; 
  int i;
  for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
    desc = ext2_get_group_desc (EXT2_SB(sb), i, NULL);
    if (!desc)
      continue;
    desc_count += desc->bg_free_blocks_count;
  }
  return desc_count;
}

unsigned long ext2_count_free_inodes (struct super_block * sb)
{ 
  struct ext2_group_desc *desc;
  unsigned long desc_count = 0;
  int i;  
  for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {
    desc = ext2_get_group_desc (EXT2_SB(sb), i, NULL);
    if (!desc)
      continue;
    desc_count += desc->bg_free_inodes_count;
  }
  return desc_count;
}

static BOOLEAN ext2_init(struct super_block *sb, dev_t dev)
{
	struct buf_head *bh=NULL;
	struct ext2_sb_info *sbi;
	struct ext2_super_block *es;
	u8_t *es_temp = NULL;
	int db_count;
	int i;
	unsigned long block;
	unsigned long def_mount_opts;

	/*
	 *FIXME
 	 *Default super block number (logical).
	 *We do not support ext2 filesystems which are configured in 
	 * a non-standard way.
	 */
	unsigned long sb_block = SB_BLOCK;
	sbi = (struct ext2_sb_info *)kmalloc(sizeof(struct ext2_sb_info),0);
	if(!sbi){
		printk("kmalloc error. %s %s\n",__func__,__FILE__);
		BUG();
	}

	sb->s_filesystem = &ext2_filesystem;
	sb->s_data = sbi;
	sbi->s_sb_block = sb_block;

	/*
	 *Read the ext2 superblock.
	 *sb_block is the logical block number.
	 *We need to convert it into sector number for sd_bread.
	 */
	bh = sd_bread(dev,0);
	es_temp = (u8_t*) get_one_page();
	if(!bh || !es_temp){
		printk("failed to get memory. %s %s\n",__func__,__FILE__);
		BUG();
	}

	//es = (struct ext2_super_block *) (bh->b_data);
	memcpy(es_temp,bh->b_data,EXT2_BLOCK_SIZE);
	es = (struct ext2_super_block *)(es_temp + 1024);
	if(es->s_magic != EXT2_SUPER_MAGIC) {
		printk("Can not find ext2 file system.\n");
		goto cantfind_ext2;
	}

	if(es->s_log_block_size != 2){
		printk("Sorry, we do not support ext2 filesystem with block size other than %d bytes.\n",EXT2_BLOCK_SIZE);
		goto cantfind_ext2;
	}
	sbi->s_es = es;

  /* Set defaults before we parse the mount options */
  def_mount_opts = es->s_default_mount_opts;
  if (def_mount_opts & EXT2_DEFM_DEBUG)
    set_opt(sbi->s_mount_opt, DEBUG);
  if (def_mount_opts & EXT2_DEFM_BSDGROUPS)
    set_opt(sbi->s_mount_opt, GRPID);
  if (def_mount_opts & EXT2_DEFM_UID16)
    set_opt(sbi->s_mount_opt, NO_UID32);
 
  if (sbi->s_es->s_errors == EXT2_ERRORS_PANIC)
    set_opt(sbi->s_mount_opt, ERRORS_PANIC);
  else if (sbi->s_es->s_errors == EXT2_ERRORS_CONTINUE)
    set_opt(sbi->s_mount_opt, ERRORS_CONT);
  else 
    set_opt(sbi->s_mount_opt, ERRORS_RO);

  sbi->s_resuid = es->s_def_resuid;
  sbi->s_resgid = es->s_def_resgid;
  
  set_opt(sbi->s_mount_opt, RESERVATION);

	//We do not use the new Orllov allocator for now,
	// because we do not have a good enough random bytes generator yet.
	set_opt(sbi->s_mount_opt, OLDALLOC);

  if (es->s_rev_level == EXT2_GOOD_OLD_REV) {
    sbi->s_inode_size = EXT2_GOOD_OLD_INODE_SIZE;
    sbi->s_first_ino = EXT2_GOOD_OLD_FIRST_INO;
  } else {
    sbi->s_inode_size = es->s_inode_size;
    sbi->s_first_ino = es->s_first_ino;
    if ((sbi->s_inode_size < EXT2_GOOD_OLD_INODE_SIZE) ||
        !is_power_of_2(sbi->s_inode_size) ||
        (sbi->s_inode_size > EXT2_BLOCK_SIZE)) {
      printk("error: unsupported inode size: %d",
        sbi->s_inode_size);
			goto cantfind_ext2;
    }    
  }

  sbi->s_frag_size = EXT2_MIN_FRAG_SIZE <<
           es->s_log_frag_size;
  if (sbi->s_frag_size == 0)
    goto cantfind_ext2;
  sbi->s_frags_per_block = EXT2_BLOCK_SIZE / sbi->s_frag_size;

  sbi->s_blocks_per_group = es->s_blocks_per_group;
  sbi->s_frags_per_group = es->s_frags_per_group;
  sbi->s_inodes_per_group = es->s_inodes_per_group;

  sbi->s_inodes_per_block = EXT2_BLOCK_SIZE / sbi->s_inode_size;
  if (sbi->s_inodes_per_block == 0 || sbi->s_inodes_per_group == 0)
    goto cantfind_ext2;
  sbi->s_itb_per_group = sbi->s_inodes_per_group /
          sbi->s_inodes_per_block;
  sbi->s_desc_per_block = EXT2_BLOCK_SIZE /
          sizeof (struct ext2_group_desc);
  sbi->s_sbh_cnix = bh;
  sbi->s_mount_state = es->s_state;
  sbi->s_addr_per_block_bits =
    ilog2 (EXT2_BLOCK_SIZE / (sizeof(unsigned long)));
  sbi->s_desc_per_block_bits =
    ilog2 (sbi->s_desc_per_block);

  if (EXT2_BLOCK_SIZE != sbi->s_frag_size) {
    printk("error: fragsize %lu != blocksize %lu"
      "(not supported yet)",
      sbi->s_frag_size, EXT2_BLOCK_SIZE);
    goto cantfind_ext2;
  }  

  if (sbi->s_blocks_per_group > EXT2_BLOCK_SIZE * 8) {
      printk("error: #blocks per group too big: %lu",
      sbi->s_blocks_per_group);
    goto cantfind_ext2;
  }
  if (sbi->s_frags_per_group > EXT2_BLOCK_SIZE * 8) {
      printk("error: #fragments per group too big: %lu",
      sbi->s_frags_per_group);
    goto cantfind_ext2;
  }
  if (sbi->s_inodes_per_group > EXT2_BLOCK_SIZE * 8) {
      printk("error: #inodes per group too big: %lu",
      sbi->s_inodes_per_group);
    goto cantfind_ext2;
  }

  sbi->s_groups_count = ((es->s_blocks_count -
        es->s_first_data_block - 1)
          / sbi->s_blocks_per_group) + 1;
  db_count = (sbi->s_groups_count + sbi->s_desc_per_block - 1) /
       sbi->s_desc_per_block;
	//printk("db_count: %d desc_per_block: %d groups_count: %d\n",db_count,sbi->s_desc_per_block,sbi->s_groups_count);

  //sbi->s_group_desc = (struct buf_head **)kmalloc (db_count * sizeof (struct buf_head *), 0);
  sbi->s_group_desc = (u8_t **)kmalloc (db_count * sizeof (u8_t*), 0);
  if (sbi->s_group_desc == NULL) {
    printk("error: not enough memory");
    goto cantfind_ext2;
  }

  sbi->s_debts = (u8_t*)kmalloc(sbi->s_groups_count*sizeof(u8_t), 0);
  if (!sbi->s_debts) {
    printk("error: not enough memory");
    goto cantfind_ext2;
  }
  for (i = 0; i < db_count; i++) {
		/*
		 *Note: we can not hold a buffer permenantly.
		 */
		struct buf_head *b=NULL;
		/*
		 *Group descriptors start from block 1.
		 *If block size is 4096 bytes, the super block should be in block 0.
		 *If block size is 1024 bytes, the super block should be block 1.
		 */
    block = descriptor_loc(sbi, 0, i);
    b = sd_bread(dev, block*EXT2_BLOCK_GRAN);
		sbi->s_group_desc[i] = (u8_t*)get_one_page();
    if (!sbi->s_group_desc[i] || !b) {
      printk("error: unable to read group descriptors");
			BUG();
    }
		memcpy(sbi->s_group_desc[i],b->b_data,EXT2_BLOCK_SIZE);
		brelse(b);
  }
  if (!ext2_check_descriptors (sbi)) {
    printk("group descriptors corrupted\n");
    goto cantfind_ext2;
  }

  sbi->s_gdb_count = db_count;

#if 0
	//Let's keep this for now, just in case we need them to do 
	// a little debugging later.
	//We will remove this when the file system gets stable.
	extern struct buf_head *read_block_bitmap(struct super_block *sb,unsigned int block_group);
	sb->s_dev = dev;
	printk("dev: %x\n",sb->s_dev);
	read_block_bitmap(sb,35);
	printk("KAKA test finished.\n");
	BUG();
#endif

  /* per fileystem reservation list head & lock */
  sbi->s_rsv_window_root = RB_ROOT;
  /*
   * Add a single, static dummy reservation to the start of the
   * reservation window list --- it gives us a placeholder for
   * append-at-start-of-list which makes the allocation logic
   * _much_ simpler.
   */
  sbi->s_rsv_window_head.rsv_start = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
  sbi->s_rsv_window_head.rsv_end = EXT2_RESERVE_WINDOW_NOT_ALLOCATED;
  sbi->s_rsv_window_head.rsv_alloc_hit = 0; 
  sbi->s_rsv_window_head.rsv_goal_size = 0; 
  ext2_rsv_window_add(sb, &sbi->s_rsv_window_head);

  sbi->s_freeblocks_counter = ext2_count_free_blocks(sb);
  sbi->s_freeinodes_counter = ext2_count_free_inodes(sb);
  sbi->s_dirs_counter = ext2_count_dirs(sb);
	
	brelse(bh); 
	return TRUE;
cantfind_ext2:
	brelse(bh);	
	printk("error while loading ext2 super block.\n");
	BUG();
	return FALSE;
}

static void ext2_sync_super(struct super_block *sb, struct ext2_super_block *es)
{
	//struct buf_head *bh = EXT2_SB(sb)->s_sbh;
	struct buf_head *bh = NULL;
	u8_t *es_temp = NULL;

  es->s_free_blocks_count = ext2_count_free_blocks(sb);
  es->s_free_inodes_count = ext2_count_free_inodes(sb);
  es->s_wtime = curclock();

	bh = sd_bread(sb->s_dev,0);
	if(!bh){
		printk("unable to get the super block. %s %s\n",__func__,__FILE__);
		BUG();
	}
	es_temp = (u8_t*)(((u8_t*)es)-1024);
	memcpy(bh->b_data,es_temp,EXT2_BLOCK_SIZE);
	bh->b_flags |= B_DIRTY;
	brelse(bh);
}

void ext2_sync()
{
	struct super_block *sb;
	struct ext2_sb_info *sbi;

	sb = get_sb(ROOT_DEV);
	if(!sb){
		printk("Failed to get the super block for dev: %x %s %s\n",ROOT_DEV,__func__,__FILE__);
		BUG();
	}
	sbi = (struct ext2_sb_info*)sb->s_data;
	ext2_sync_super(sb,sbi->s_es);
}

static void ext2_free(struct super_block *sb)
{
	struct ext2_sb_info *sbi;
	struct ext2_super_block *es;
	//u8_t *es_temp=NULL;
	//struct buf_head *bh;
  int db_count;
  int i;

	sbi = (struct ext2_sb_info *)sb->s_data;
	es = sbi->s_es;

	if(!sb->s_roflag){
  	es->s_state = sbi->s_mount_state;
	  ext2_sync_super(sb,es);
	}else {
		printk("ext2 filesystem mounted in readonly mode. %s %s\n",
			__func__,__FILE__);
		BUG();
	}

  db_count = sbi->s_gdb_count;
  for (i = 0; i < db_count; i++){
		if(sbi->s_group_desc[i]){
			struct buf_head *b=NULL;
			unsigned long block;
			/*
			 *Group descriptors start from block 1.
			 *If block size is 4096 bytes, the super block should be in block 0.
			 *If block size is 1024 bytes, the super block should be block 1.
			 */
    	block = descriptor_loc(sbi, 0, i);
    	b = sd_bread(sb->s_dev, block*EXT2_BLOCK_GRAN);
    	if (!b) {
    	  printk("error: unable to read group descriptors");
				BUG();
    	}
			memcpy(b->b_data,sbi->s_group_desc[i],EXT2_BLOCK_SIZE);
			b->b_flags |= B_DIRTY;
			brelse(b);
			free_one_page((unsigned long)(sbi->s_group_desc[i]),0);
		}
	}
  kfree(sbi->s_group_desc);
  kfree(sbi->s_debts);
#if 0
  //brelse (sbi->s_sbh);
	bh = sd_bread(sb->s_dev,0);
	if(!bh){
		printk("unable to get the super block. %s %s\n",__func__,__FILE__);
		BUG();
	}
	es_temp = (u8_t*)(((u8_t*)sbi->s_es)-1024);
	memcpy(bh->b_data,es_temp,EXT2_BLOCK_SIZE);
	bh->b_flags |= B_DIRTY;
	brelse(bh);
#endif
  sb->s_data = NULL;
  kfree(sbi);
}

static struct ext2_inode *ext2_get_inode(struct super_block *sb, ino_t ino,
          struct buf_head **p)
{
  struct buf_head * bh;
  unsigned long block_group;
  unsigned long block;
  unsigned long offset;
  struct ext2_group_desc * gdp;

  *p = NULL;
  if ((ino != EXT2_ROOT_INO && ino < EXT2_FIRST_INO(sb)) ||
      ino > (EXT2_SB(sb)->s_es->s_inodes_count)){
		printk("invalid ext2 inode number. %s %s\n",__func__,__FILE__);
		BUG();
	}

  block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb);
  gdp = ext2_get_group_desc(sb->s_data, block_group, NULL);
  if (!gdp){
		printk("failed to get ext2 group descriptor. %s %s\n",
			__func__,__FILE__);
		BUG();
	}
  /*
   * Figure out the offset within the block group inode table
   */
  offset = ((ino - 1) % EXT2_INODES_PER_GROUP(sb)) * EXT2_INODE_SIZE(sb);
  block = gdp->bg_inode_table +
    (offset >> EXT2_BLOCK_BITS); //EXT2_BLOCK_SIZE_BITS(sb));
  if (!(bh = sd_bread(sb->s_dev, block*EXT2_BLOCK_GRAN))){
		printk("ext2 inode read failed. %s %s\n",__func__,__FILE__);
		BUG();
	}

  *p = bh;
  offset &= (EXT2_BLOCK_SIZE - 1);
  return (struct ext2_inode *) (bh->b_data + offset);
}

static BOOLEAN ext2_iread(struct inode *inoptr, dev_t dev, ino_t ino)
{
	struct ext2_inode_info *ei;
	struct ext2_inode *raw_inode;
	struct buf_head *bh;
	int n;

	ei = (struct ext2_inode_info *)kmalloc(sizeof(*ei),PageWait);
	if(!ei){
		printk("out of memory for %s %s\n",__func__,__FILE__);
		BUG();
	}

  raw_inode = ext2_get_inode(inoptr->i_sb, ino, &bh);
  if (IS_ERR(raw_inode)) {
		printk("Invalid raw inode pointer. %s %s\n",
			__func__,__FILE__);
		BUG();
  }

	memcpy(&ei->ext2_raw_inode,raw_inode,sizeof(struct ext2_inode));
  ei->i_flags = raw_inode->i_flags;
  ei->i_faddr = raw_inode->i_faddr;
  ei->i_frag_no = raw_inode->i_frag;
  ei->i_frag_size = raw_inode->i_fsize;
  ei->i_file_acl = raw_inode->i_file_acl;
  ei->i_dir_acl = 0;
	ei->i_size = raw_inode->i_size;
  if (!S_ISREG(raw_inode->i_mode)){
    ei->i_dir_acl = raw_inode->i_dir_acl;
  }else
    ei->i_size |= ((u64_t)le32_to_cpu(raw_inode->i_size_high)) << 32;

  ei->i_dtime = 0;
  ei->i_state = 0;
  ei->i_block_group = (ino - 1) / EXT2_INODES_PER_GROUP(inoptr->i_sb); 
  ei->i_dir_start_lookup = 0;

  for (n = 0; n < EXT2_N_BLOCKS; n++)
    ei->I_data[n] = raw_inode->i_block[n];

	brelse(bh);
	inoptr->i_ops = &ext2_inode_operation;
	inoptr->i_data = ei;
	return TRUE;
}

void ext2_update_dynamic_rev(struct super_block *sb)
{       
  struct ext2_super_block *es = EXT2_SB(sb)->s_es;
        
  if (es->s_rev_level > EXT2_GOOD_OLD_REV)
    return;
    
  printk("warning: updating to rev %d because of "
         "new feature flag, running e2fsck is recommended\n",
         EXT2_DYNAMIC_REV);
	printk("I guess you have created a very large file.\n");

	BUG();    
  es->s_first_ino = (EXT2_GOOD_OLD_FIRST_INO);
  es->s_inode_size = (EXT2_GOOD_OLD_INODE_SIZE);
  es->s_rev_level = (EXT2_DYNAMIC_REV);
  /* leave es->s_feature_*compat flags alone */
  /* es->s_uuid will be set by e2fsck if empty */
      
  /*    
   * The rest of the superblock fields should be zero, and if not it
   * means they are likely already in use, so leave them alone.  We
   * can leave it up to e2fsck to clean up any inconsistencies there.
   */
}

static BOOLEAN ext2_iwrite(struct inode *inoptr,dev_t dev,ino_t inode)
{
	struct ext2_inode_info *ei = inoptr->i_data;
	struct super_block *sb = inoptr->i_sb;
	int n;
	struct buf_head *bh;
	struct ext2_inode *raw_inode = ext2_get_inode(sb,inode,&bh);

	if(IS_ERR(raw_inode)){
		printk("getting ext2 inode failed. %s %s\n",__func__,__FILE__);
		BUG();
	}

	memcpy(raw_inode,&ei->ext2_raw_inode,sizeof(struct ext2_inode));
  raw_inode->i_dtime = ei->i_dtime;
  raw_inode->i_flags = ei->i_flags;
  raw_inode->i_faddr = ei->i_faddr;
  raw_inode->i_frag = ei->i_frag_no;
  raw_inode->i_fsize = ei->i_frag_size;
  raw_inode->i_file_acl = ei->i_file_acl;
	raw_inode->i_size = ei->i_size;
 
 if (!S_ISREG(ei->ext2_raw_inode.i_mode)){
    raw_inode->i_dir_acl = cpu_to_le32(ei->i_dir_acl);
  }else {
		raw_inode->i_size_high = ei->i_size >> 32;
    if (ei->i_size > 0x7fffffffULL) {
      if (!EXT2_HAS_RO_COMPAT_FEATURE(EXT2_SB(sb),
          EXT2_FEATURE_RO_COMPAT_LARGE_FILE) ||
          EXT2_SB(sb)->s_es->s_rev_level ==
          EXT2_GOOD_OLD_REV) {
             /* If this is the first large file
        * created, add a flag to the superblock.
        */
        ext2_update_dynamic_rev(sb);
        EXT2_SET_RO_COMPAT_FEATURE(EXT2_SB(sb),
          EXT2_FEATURE_RO_COMPAT_LARGE_FILE);
        ext2_sync_super(sb,EXT2_SB(sb)->s_es);
      }
    }
  }

  raw_inode->i_generation = ei->ext2_raw_inode.i_generation;
  /*if (S_ISCHR(ei->ext2_raw_inode.i_mode) || S_ISBLK(ei->ext2_raw_inode.i_mode)) {
    raw_inode->i_block[0] =
      inoptr->i_dev;
    raw_inode->i_block[1] = 0;
  } else */
  if (!S_ISCHR(ei->ext2_raw_inode.i_mode) && !S_ISBLK(ei->ext2_raw_inode.i_mode)) {
		for (n = 0; n < EXT2_N_BLOCKS; n++)
    	raw_inode->i_block[n] = ei->I_data[n];
	}
	
	bh->b_flags |= B_DIRTY;
	brelse(bh);	
	return TRUE;
}

/*
 * There are two policies for allocating an inode.  If the new inode is
 * a directory, then a forward search is made for a block group with both
 * free space and a low directory-to-inode ratio; if that fails, then of
 * the groups with above-average free space, that group with the fewest
 * directories already is chosen.
 *
 * For other inodes, search forward from the parent directory\'s block
 * group to find a free inode.
 */
static int find_group_dir(struct super_block *sb, struct inode *parent)
{
  int ngroups = EXT2_SB(sb)->s_groups_count;
  int avefreei = ext2_count_free_inodes(sb) / ngroups;
  struct ext2_group_desc *desc, *best_desc = NULL;
  int group, best_group = -1;

  for (group = 0; group < ngroups; group++) {
    desc = ext2_get_group_desc (EXT2_SB(sb), group, NULL);
    if (!desc || !desc->bg_free_inodes_count)
      continue;
    if (desc->bg_free_inodes_count < avefreei)
      continue;
    if (!best_desc ||
        (desc->bg_free_blocks_count >
         best_desc->bg_free_blocks_count)) {
      best_group = group;
      best_desc = desc;
    }
  }
  if (!best_desc)
    return -1;

  return best_group;
}

static int find_group_other(struct super_block *sb, struct inode *parent)
{
  int parent_group = EXT2_I(parent)->i_block_group;
  int ngroups = EXT2_SB(sb)->s_groups_count;
  struct ext2_group_desc *desc;
  int group, i;

  /*
   * Try to place the inode in its parent directory
   */
  group = parent_group;
  desc = ext2_get_group_desc (EXT2_SB(sb), group, NULL);
  if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
      le16_to_cpu(desc->bg_free_blocks_count))
    goto found;

  /*
   * We're going to place this inode in a different blockgroup from its
   * parent.  We want to cause files in a common directory to all land in
   * the same blockgroup.  But we want files which are in a different
   * directory which shares a blockgroup with our parent to land in a
   * different blockgroup.
   *
   * So add our directory's i_ino into the starting point for the hash.
   */
  group = (group + parent->i_num) % ngroups;

  /*
   * Use a quadratic hash to find a group with a free inode and some
   * free blocks.
   */
  for (i = 1; i < ngroups; i <<= 1) {
    group += i;
    if (group >= ngroups)
      group -= ngroups;
    desc = ext2_get_group_desc (EXT2_SB(sb), group, NULL);
    if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
        le16_to_cpu(desc->bg_free_blocks_count))
      goto found;
  }

  /*
   * That failed: try linear search for a free inode, even if that group
   * has no free blocks.
   */
  group = parent_group;
  for (i = 0; i < ngroups; i++) {
    if (++group >= ngroups)
      group = 0;
    desc = ext2_get_group_desc (EXT2_SB(sb), group, NULL);
    if (desc && le16_to_cpu(desc->bg_free_inodes_count))
      goto found;
  }
  return -1;

found:
  return group;
}

/*
 * The free inodes are managed by bitmaps.  A file system contains several
 * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
 * block for inodes, N blocks for the inode table and data blocks.
 *
 * The file system contains group descriptors which are located after the
 * super block.  Each descriptor contains the number of the bitmap block and
 * the free blocks count in the block.
 */


/*
 * Read the inode allocation bitmap for a given block_group, reading
 * into the specified slot in the superblock's bitmap cache.
 *
 * Return buffer_head of bitmap on success or NULL.
 */
static struct buf_head *
read_inode_bitmap(struct super_block * sb, unsigned long block_group)
{
  struct ext2_group_desc *desc;
  struct buf_head *bh = NULL;

  desc = ext2_get_group_desc(EXT2_SB(sb), block_group, NULL);
  if (!desc)
    goto error_out;

  bh = sd_bread(sb->s_dev, le32_to_cpu(desc->bg_inode_bitmap)*EXT2_BLOCK_GRAN);
  if (!bh)
    printk("read_inode_bitmap",
          "Cannot read inode bitmap - "
          "block_group = %lu, inode_bitmap = %u",
          block_group, le32_to_cpu(desc->bg_inode_bitmap));
error_out:
  return bh;
}

#define ___constant_swab32(x) ((u32_t)(       \
  (((u32_t)(x) & (u32_t)0x000000ffUL) << 24) |    \
  (((u32_t)(x) & (u32_t)0x0000ff00UL) <<  8) |    \
  (((u32_t)(x) & (u32_t)0x00ff0000UL) >>  8) |    \
  (((u32_t)(x) & (u32_t)0xff000000UL) >> 24)))

static inline unsigned long ext2_swabp(const unsigned long * x)
{
#if BITS_PER_LONG == 32
  return (unsigned long) ___constant_swab32(*((u32_t *) x));
#else
#error BITS_PER_LONG not defined
#endif
}

/* include/linux/byteorder doesn't support "unsigned long" type */
static inline unsigned long ext2_swab(const unsigned long y)
{
#if BITS_PER_LONG == 32
  return (unsigned long) ___constant_swab32((u32_t) y);
#else
#error BITS_PER_LONG not defined
#endif
}

#define BITOP_WORD(nr)    ((nr) / BITS_PER_LONG)
unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
    long size, unsigned long offset)
{
  const unsigned long *p = addr + BITOP_WORD(offset);
  unsigned long result = offset & ~(BITS_PER_LONG - 1);
  unsigned long tmp;

  if (offset >= size)
    return size;
  size -= result;
  offset &= (BITS_PER_LONG - 1UL);
  if (offset) {
    tmp = ext2_swabp(p++);
    tmp |= (~0UL >> (BITS_PER_LONG - offset));
    if (size < BITS_PER_LONG)
      goto found_first;
    if (~tmp)
      goto found_middle;
    size -= BITS_PER_LONG;
    result += BITS_PER_LONG;
  }

  while (size & ~(BITS_PER_LONG - 1)) {
    if (~(tmp = *(p++)))
      goto found_middle_swap;
    result += BITS_PER_LONG;
    size -= BITS_PER_LONG;
  }
  if (!size)
    return result;
  tmp = ext2_swabp(p);
found_first:
  tmp |= ~0UL << size;
  if (tmp == ~0UL)  /* Are any bits zero? */
    return result + size; /* Nope. Skip ffz */
found_middle:
  return result + ffz(tmp);

found_middle_swap:
  return result + ffz(ext2_swab(tmp));
}

unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
         unsigned long offset)
{
  const unsigned long *p = addr + BITOP_WORD(offset);
  unsigned long result = offset & ~(BITS_PER_LONG-1);
  unsigned long tmp;

  if (offset >= size)
    return size;
  size -= result;
  offset %= BITS_PER_LONG;
  if (offset) {
    tmp = *(p++);
    tmp |= ~0UL >> (BITS_PER_LONG - offset);
    if (size < BITS_PER_LONG)
      goto found_first;
    if (~tmp)
      goto found_middle;
    size -= BITS_PER_LONG;
    result += BITS_PER_LONG;
  }
  while (size & ~(BITS_PER_LONG-1)) {
    if (~(tmp = *(p++)))
      goto found_middle;
    result += BITS_PER_LONG;
    size -= BITS_PER_LONG;
  }
  if (!size)
    return result;
  tmp = *p; 

found_first:
  tmp |= ~0UL << size;
  if (tmp == ~0UL)  /* Are any bits zero? */
    return result + size; /* Nope. */
found_middle:
  return result + ffz(tmp);
}

static BOOLEAN ext2_ialloc(void *data, struct inode *inoptr, mode_t mode)
{
	struct inode *dir = (struct inode *)data;
	struct ext2_inode_info *ei;
	struct ext2_group_desc *gdp;
	struct buf_head *bitmap_bh=NULL;
	u8_t *bh2;
	struct super_block *sb;
	struct ext2_sb_info *sbi;
	struct ext2_super_block *es;
	ino_t ino=0;
	int group=0;
	int i;

	sb = dir->i_sb;
	sbi = sb->s_data;
	es = sbi->s_es;

	ei = (struct ext2_inode_info *)kmalloc(sizeof(struct ext2_inode_info),PageWait);
	if(!ei){
		printk("out of memory. %s %s\n",__func__,__FILE__);
		BUG();
	}

	memset(ei, 0x0, sizeof(struct ext2_inode_info));

  if (S_ISDIR(mode)) {
    if (test_opt(sb, OLDALLOC))
      group = find_group_dir(sb, dir);
    else{
			printk("Orlov's allocator not supported yet. \n");
			printk("mount_opt: %x\n",EXT2_SB(sb)->s_mount_opt);
			BUG();
      group = find_group_dir(sb, dir);
      //group = find_group_orlov(sb, dir);
		}
  } else 
    group = find_group_other(sb, dir);

  if (group == -1) {
		printk("failed to get group number. %s %s\n",__func__,__FILE__);
		BUG();
  }
	
  for (i = 0; i < sbi->s_groups_count; i++) {
    gdp = ext2_get_group_desc(EXT2_SB(sb), group, &bh2);
    brelse(bitmap_bh);
    bitmap_bh = read_inode_bitmap(sb, group);
    if (!bitmap_bh) {
			printk("reading inode bitmap error. %s %s\n",__func__,__FILE__);
			BUG();
    }
    ino = 0;

repeat_in_this_group:
    ino = ext2_find_next_zero_bit((unsigned long *)bitmap_bh->b_data,
                EXT2_INODES_PER_GROUP(sb), ino);
    if (ino >= EXT2_INODES_PER_GROUP(sb)) {
      /*
       * Rare race: find_group_xx() decided that there were
       * free inodes in this group, but by the time we tried
       * to allocate one, they're all gone.  This can also
       * occur because the counters which find_group_orlov()
       * uses are approximate.  So just go and search the
       * next block group.
       */
      if (++group == sbi->s_groups_count)
        group = 0;
      continue;
    }
    if (ext2_set_bit_atomic(sb_bgl_lock(sbi, group),
            ino, bitmap_bh->b_data)) {
      /* we lost this inode */
      if (++ino >= EXT2_INODES_PER_GROUP(sb)) {
        /* this group is exhausted, try next group */
        if (++group == sbi->s_groups_count)
          group = 0;
        continue;
      }
      /* try to find free inode in the same group */
      goto repeat_in_this_group;
    }
    goto got;
  }

  /*
   * Scanned all blockgroups.
   */
	printk("failed to get ino after all blockgroups have been scanned. %s %s\n",
		__func__,__FILE__);
	BUG();

got:
	bitmap_bh->b_flags |= B_DIRTY;
	brelse(bitmap_bh);

  ino += group * EXT2_INODES_PER_GROUP(sb) + 1;
  if (ino < EXT2_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
    printk( "ext2_new_inode error",
          "reserved inode or inode > inodes count - "
          "block_group = %d,inode=%lu", group,
          (unsigned long) ino);
		BUG();
  }

  sbi->s_freeinodes_counter--;;
  if (S_ISDIR(mode))
    sbi->s_dirs_counter++;
  
  gdp->bg_free_inodes_count--;
  if (S_ISDIR(mode)) {
    if (sbi->s_debts[group] < 255)
      sbi->s_debts[group]++;
    gdp->bg_used_dirs_count++;
  } else {
    if (sbi->s_debts[group])
      sbi->s_debts[group]--;
  } 

	//bh2->b_flags |= B_DIRTY;
	memset(ei->I_data, 0, sizeof(ei->I_data));
  ei->i_flags =
    ext2_mask_flags(mode, EXT2_I(dir)->i_flags & EXT2_FL_INHERITED);
  ei->i_faddr = 0;
  ei->i_frag_no = 0;
  ei->i_frag_size = 0;
  ei->i_file_acl = 0; 
  ei->i_dir_acl = 0;
  ei->i_dtime = 0;
  ei->i_size = 0;
  ei->i_block_alloc_info = NULL;
  ei->i_block_group = group;
  ei->i_dir_start_lookup = 0;
  ei->i_state = EXT2_STATE_NEW;

	ei->ext2_raw_inode.i_mode = mode;
	ei->ext2_raw_inode.i_links_count = 1;
	ei->ext2_raw_inode.i_uid = current->euid;
	ei->ext2_raw_inode.i_gid = current->egid;
	ei->ext2_raw_inode.i_size = 0;
	ei->ext2_raw_inode.i_atime = curclock();
	ei->ext2_raw_inode.i_ctime = curclock();
	ei->ext2_raw_inode.i_mtime = curclock();

	inoptr->i_dev = sb->s_dev;
	inoptr->i_num = ino;
	inoptr->i_ops = &ext2_inode_operation;
	inoptr->i_data = ei;	
	return TRUE;
}

static void ext2_release_inode(struct super_block *sb, int group, int dir)
{
  struct ext2_group_desc * desc;
  //struct buf_head *bh;
	u8_t *bh;

  desc = ext2_get_group_desc(EXT2_SB(sb), group, &bh);
  if (!desc) {
    printk("ext2_release_inode",
      "can't get descriptor for group %d", group);
    BUG();
  }

  desc->bg_free_inodes_count++;
  if (dir)
    desc->bg_used_dirs_count--;
  if (dir)
    EXT2_SB(sb)->s_dirs_counter--;
	//bh->b_flags |= B_DIRTY;
}

static void ext2_ifree(struct super_block *sb, struct inode *inode)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;
	struct ext2_super_block *es;
  struct buf_head *bitmap_bh = NULL;
  unsigned long block_group;
  unsigned long bit;
	int is_directory;
	ino_t ino = inode->i_num;

	if(inode->i_sb != sb){
		printk("freeing invalid inode. %s %s\n",__func__,__FILE__);
		BUG();
	}

	if(sb->s_dev == NODEV){
		printk("Freeing invalid super block. %s %s\n",__func__,__FILE__);
		BUG();
	}

	if(sb->s_roflag)
		return;

	es = EXT2_SB(sb)->s_es;
	if(!es){
		printk("Freeing invalid ext2 super block. %s %s\n",
			__func__,__FILE__);
		BUG();
	}	

  if (ino < EXT2_FIRST_INO(sb) ||
      ino > le32_to_cpu(es->s_inodes_count)) {
    printk("ext2_free_inode",
          "reserved or nonexistent inode %lu", ino);
		BUG();
  }

loop:
	// lock super block
	if(sb->s_flags & LOCK_BITOP){
		sb->s_flags |= WANT_BITOP;
		sleepon(&sb->s_bitop_wait);

		goto loop;
	}

  is_directory = S_ISDIR(ei->ext2_raw_inode.i_mode);
	sb->s_flags |= LOCK_BITOP;

  block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb);
  bit = (ino - 1) % EXT2_INODES_PER_GROUP(sb);
  brelse(bitmap_bh);
  bitmap_bh = read_inode_bitmap(sb, block_group);
  if (!bitmap_bh){
		printk("bitmap_bf should exist. %s %s\n",__func__,__FILE__);
		BUG();
	}

  /* Ok, now we can actually update the inode bitmaps.. */
  if (!ext2_clear_bit_atomic(sb_bgl_lock(EXT2_SB(sb), block_group),
        bit, (void *) bitmap_bh->b_data)){
    printk("ext2_free_inode",
           "bit already cleared for inode %lu", ino);
		BUG();
  }else
    ext2_release_inode(sb, block_group, is_directory);

 	bitmap_bh->b_flags |= B_DIRTY;
	brelse(bitmap_bh);

	// unlock super block
	sb->s_flags &= ~(LOCK_BITOP);
	if(sb->s_flags & WANT_BITOP){
		sb->s_flags &= ~WANT_BITOP;
		wakeup(&sb->s_bitop_wait);
	}
}

static unsigned long ext2_balloc(void* data)
{
	struct inode *inode = (struct inode*)data;
	unsigned long count = 1;

	return ext2_new_blocks(inode,-1,&count);
}

static void ext2_bfree(void *data, unsigned long b)
{
	struct inode *inode = (struct inode *)data;
	ext2_free_blocks(inode,b,1);
}
	
static int ext2_statfs(struct super_block *sb, struct statfs * ext2_stat)
{
	struct ext2_sb_info *sbi = EXT2_SB(sb);
	struct ext2_super_block *es = sbi->s_es;

	ext2_stat->f_type = es->s_magic;
	ext2_stat->f_bsize = EXT2_BLOCK_SIZE;
	ext2_stat->f_blocks = es->s_blocks_count;
	ext2_stat->f_bfree = es->s_free_blocks_count;
	ext2_stat->f_bavail = es->s_free_blocks_count;
	ext2_stat->f_files = es->s_inodes_count;
	ext2_stat->f_ffree = es->s_free_inodes_count;
	ext2_stat->f_namelen = 255;

	return 0;
}
